| 翻訳と辞書 |
| L (complexity) ： ウィキペディア英語版 |
L (complexity)
In computational complexity theory, L (also known as LSPACE or DLOGSPACE) is the complexity class containing decision problems that can be solved by a deterministic Turing machine using a logarithmic amount of memory space.〔, Definition 8.12, p. 295.〕〔, p. 177.〕 Logarithmic space is sufficient to hold a constant number of pointers into the input〔 and a logarithmic number of boolean flags, and many basic logspace algorithms use the memory in this way.
==Complete problems and logical characterization==
Every non-trivial problem in L is complete under log-space reductions,〔See , Theorem 7.13 (claim 2), p. 179.〕 so weaker reductions are required to identify meaningful notions of L-completeness, the most common being first-order reductions.
A 2004 result by Omer Reingold shows that USTCON, the problem of whether there exists a path between two vertices in a given undirected graph, is in L, showing that L = SL, since USTCON is SL-complete.
One consequence of this is a simple logical characterization of L: it contains precisely those languages expressible in first-order logic with an added commutative transitive closure operator (in graph theoretical terms, this turns every connected component into a clique). This result has application to database query languages: ''data complexity'' of a query is defined as the complexity of answering a fixed query considering the data size as the variable input. For this measure, queries against relational databases with complete information (having no notion of nulls) as expressed for instance in relational algebra are in L.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「L (complexity)」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|